#include <vector>


//插入排序，平均时间复杂度O(n^2),空间复杂度O(1),稳定
void Insertion_sort(vector<int> &nums){
    int temp = 0,i = 0,j = 0;
    for(i = 1;i < nums.size();i++){
        if(nums[i-1] > nums[i]){
            temp = nums[i];
            for(j = i - 1;j >= 0 && nums[j] > temp ;j--){
                nums[j+1] = nums[j];
            }
            nums[j+1] = temp;
        }
    }
}